package com.tree;

import java.util.*;

/**
 * @Author:hanguanglei
 * @Description:
 * @Date: Created in 2020-10-07 13:50
 * @Modified By:
 */

public class TranvesalTreeNodeTool {
    //记录从根节点到某节点的路径，key为节点的名称，value为路径
    private HashMap<String, List<TreeNode>> pathMap = new HashMap<String, List<TreeNode>>();
    public void deepFirstSearch(TreeNode node) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Stack<TreeNode> pathstack = new Stack<TreeNode>();
        stack.push(node);
        while (!stack.empty()) {
            TreeNode tempNode = stack.pop();
            vist(tempNode, pathstack);
            //说明该节点有孩子节点
            if (tempNode.getChildLst() != null && tempNode.getChildLst().size() > 0) {
                Iterator<TreeNode> iterator = tempNode.getChildLst().iterator();
                while (iterator.hasNext()) {
                    stack.push(iterator.next());
                }
            }
        }
    }

    public void vist(TreeNode node, Stack<TreeNode> pathStack) {
        //保证新加入pathStack的节点 必须是‘pathStack栈顶节点’的孩子节点
        while (pathStack.size() > 0 && !isChild(node, pathStack.peek())) {
            pathStack.pop();
        }
        pathStack.push(node);
        addPath(pathStack);
        //System.out.println("访问：" + node.getNodeName());
        if (isLeaf(node)) {
            //当遇到叶子节点时，打印从根节点到叶子节点的路径
            printPath(pathStack);
        }
    }

    public void addPath(Stack<TreeNode> pathStack) {
        TreeNode top = pathStack.peek();
        if (!this.pathMap.containsKey(top.getNodeName()))
            this.pathMap.put(top.getNodeName(), new ArrayList(pathStack));
    }

    public List<TreeNode> getRootToNodePath(String name) {
        return this.pathMap.get(name);
    }

    public static boolean isChild(TreeNode node, TreeNode nodeParent) {
        if (nodeParent.getChildLst() != null && nodeParent.getChildLst().size() > 0 && nodeParent.getChildLst().contains(node))
            return true;
        else
            return false;
    }

    /**
     * 打印路径
     * @param pathStack
     */
    public static void printPath(Stack<TreeNode> pathStack) {
        Iterator<TreeNode> iterator = pathStack.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next().getNodeName() + "->");
        }
        System.out.println();
    }
    /**
     * 打印路径
     * @param  pathLst
     */
    public static void printPath(List<TreeNode> pathLst) {
        Iterator<TreeNode> iterator = pathLst.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next().getNodeName() + "->");
        }
        System.out.println();
    }

    public static boolean isLeaf(TreeNode node) {
        if (node.getChildLst() == null || node.getChildLst().size() <= 0)
            return true;
        else
            return false;
    }




    /**
     * 由于一个孩子节点只有一个父节点，所以从根节点到某一节点的路径是单向且唯一的。如果两个节点有公共的祖先，两个路径合起来应该是倒立的Y字形，
     * 如A、B两个节点所示，从根节点开始遍历两条不同的路径，当路径出现不一致时(X节点)，出现不一致之前的那个点就是最小公共父亲节点
     *
     *
     X
     *  *
     *    *
     A      *
     *
     B
     *
     *
     * @param lst1
     * @param lst2
     * @return
     * 获取共同的祖先节点
     */
    public TreeNode getLeastParentNode(List<TreeNode> lst1, List<TreeNode> lst2) {

        List<TreeNode> loogerLst = lst2;
        List<TreeNode> shorterLst = lst1;
        if (loogerLst.size() < shorterLst.size()) {
            List<TreeNode> tempLst = loogerLst;
            loogerLst = shorterLst;
            shorterLst = tempLst;
        }
        int index = 0;
        for (int i = 0; i < shorterLst.size(); i++) {
            if (shorterLst.get(i).equals(loogerLst.get(i)))
                continue;
            else {
                index = i - 1;
                break;
            }
        }
        return shorterLst.get(index);


    }

}
